1049. Last Stone Weight II
题目 1049. Last Stone Weight II
思路分析
选择任意两块互撞 要最后结果最小 显然是策略问题
那就想到dp和贪心 看看贪心能不能解出来：
模拟案例可知：
双指针 最大最小互撞 答案错误
优先队列最大两个互撞 也答案错误
看来不能简单贪心
确实有趣：
这道题的本质不是“消除”，而是把石头分成两堆。
当我们把石头 \(x\) 和 \(y\) 撞击得到 \(y-x\)，再拿去和 \(z\) 撞击得到 \(z-(y-x) = z-y+x\)...
你会发现，无论怎么撞，最终剩下的石头的重量，其实就是所有石头重量的加减组合：
\[Result = k_1 \cdot s_1 + k_2 \cdot s_2 + ... + k_n \cdot s_n\]
其中 \(k\) 只能是 \(+1\) 或 \(-1\)。
为了让结果最小（且 \(\ge 0\)），我们要把石头分成两堆（正数堆 \(P\) 和 负数堆 \(N\)），让它们的总和差值最小。
\[Target = \min(Sum_P - Sum_N)\]
这等价于：我们想从一堆石头里挑出一些，让它们的总和尽可能接近（但不超过）总重量的一半。
设所有石头总重为 sum，我们要找一个子集，其和 dp_sum 最接近 sum / 2。
最终答案就是：
\[Answer = sum - 2 \times dp\_sum\]
(解释：剩下的一半减去我们凑出来的一半)
这变成了一个经典的 0/1 背包问题：
- 背包容量：
target = sum / 2 - 物品：每块石头的重量
- 价值：每块石头的重量
- 目标：往背包里装石头，装得越满越好（但不能撑破）。
将集合分成两个子集，使得差值最小”或者“加减号组合结果最小——通常都是 0/1 背包问题 的变体。
代码实现
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int stone : stones){
sum+=stone;
}
int target = sum / 2;
int[] dp = new int[target + 1];
for(int stone : stones){
for(int j=target; j >= stone ; j--){
dp[j] = Math.max(dp[j],dp[j-stone]+stone);
}
}
return sum - 2 * dp[target];
}
}
💬 评论